//
//$Id: subset.cpp 722 2012-11-29 17:33:43Z andrew.tsyganov $
#include "stdafx.h"
#include "include/fa.h"
#include "include/subset.h"
#include "include/utils.h"

using namespace std;

bool operator <=(Subset const& lhs, Subset const& rhs) 
{ 
    if (lhs.count() > rhs.count()) 
        return false; 
    
    for (Subset::enumerator en = lhs.first(); en != lhs.end(); ++en)
        if (!rhs.contains(*en))
            return false;

    return true;
}

string Subset::to_String(Brackets_Type const bt, int const add) const
{
    if (none())
        return OpenBracket(bt) + CloseBracket(bt);

    string s = OpenBracket(bt);

    for (Subset::enumerator en = first(); en != end(); ++en)
        s += IntToString(*en + add) + ",";

    s.erase(s.length()-1);

    s += CloseBracket(bt);

    return s;
}

string Subset::to_String(FA const& a, Brackets_Type const bt) const
{
    if (none())
        return OpenBracket(bt) + CloseBracket(bt);

    string s = OpenBracket(bt);

    for (Subset::enumerator en = first(); en < end(); ++en)
        s += a.states_[*en] + ",";

    s.erase(s.length()-1);

    s += CloseBracket(bt);

    return s;
}

size_t Subset::get_By_Count(size_t const i) const
{
    size_t k = 0;
    size_t j = get_first();
    do
    {
        if (k == i)
            return j;
        ++k;
        j = get_next(j);
    }
    while (j);

#ifdef _MSC_VER
    __assume(0);
#endif
}

unsigned char* Subset::serialize(Subset_Serializer& ss, unsigned& len)
{
    optimize();  
    Subset::statistics st;
    calc_stat(&st);
    unsigned char* buf = new unsigned char[st.max_serialize_mem];
    len = ss.serialize((*this), buf, 0);

    return buf;
}

size_t Subset::to_Int() const
{
    size_t n = count();

    if (n == 0)
    {
        return 0;
    }

    size_t res = 0;
    size_t k   = 0;
    size_t i   = 0;

    do 
    {
        if (test(i))
        {
            ++k;
            res += 1 << i;
        }
        ++i;
    }
    while (k < n);

    return res;
}

bool FindInVector(std::vector<Subset> const& vs, Subset const& s, size_t& id)
{
    for (size_t i = 0; i < vs.size(); ++i)
    {
        if (vs[i] == s)
        {
            id = i;
            return true;
        }
    }

    return false;
}

void PrintVector(ostream& os, vector<Subset> const& vs)
{
    for (size_t i = 0; i < vs.size(); ++i)
    {
        os << vs[i].to_String() << " ";
    }
    os << endl;
}

bool JoinSubsets(vector<Subset> const& vs1, vector<Subset> const& vs2, vector<Subset>& vs)
{
    size_t n1 = vs1.size();
    size_t n2 = vs2.size();
    
    if (n1 != n2)
    {
        return false;
    }

    vs.reserve(n1);

    for (size_t i = 0; i < n1; ++i)
    {
        Subset s;
        for (Subset::enumerator en = vs1[i].first(); en != vs1[i].end(); ++en)
        {
            s += vs2[*en];
        }
        vs.push_back(s);
    }

    return true;
}

bool JoinSubsetsNE(vector<Subset> const& vs1, vector<Subset> const& vs2, vector<Subset>& vs)
{
    size_t n1 = vs1.size();
    size_t n2 = vs2.size();
    
    if (n1 != n2)
    {
        return false;
    }

    vs.reserve(n1);

    for (size_t i = 0; i < n1; ++i)
    {
        Subset s;
        for (Subset::enumerator en = vs1[i].first(); en != vs1[i].end(); ++en)
        {
            s += vs2[*en];
        }
        
        if (!s.empty())
        {
            vs.push_back(s);
        }
    }

    return true;
}

size_t FindEmptySet(vector<Subset> const& vs)
{
    for (size_t i = 0; i < vs.size(); ++i)
    {
        if (vs[i].empty())
        {
            return i;
        }
    }

    return vs.size();
}

size_t FindEmptySet(std::vector<Subset> const& vs1, std::vector<Subset> const& vs2)
{
    for (size_t i = 0; i < vs1.size(); ++i)
    {
        if (vs1[i].count() == 1)
        {
            if (vs2[vs1[i].get_first()].empty())
            {
                return i;
            }
        }
    }

    return vs1.size();
}

//EOF!
